/*
 * @lc app=leetcode.cn id=583 lang=golang
 *
 * [583] 两个字符串的删除操作
 */

// @lc code=start
func minDistance(word1 string, word2 string) int {
	m,n := len(word1),len(word2)
	dp := make([][]int,m+1)
	// dp 数组的内容
	for i,_:=range dp{
		dp[i] = make([]int,n+1)
		dp[i][0] = i 
	}
	for i,_:=range dp[0]{
		dp[0][i] = i
	}

	for i:=1;i<=m;i++{
		for j:=1;j<=n;j++{
			if word1[i-1] == word2[j-1]{
				dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1])+1)
			}else{
				dp[i][j] = min(dp[i-1][j-1]+2,min(dp[i-1][j],dp[i][j-1])+1)
			}
		}
	}
	return dp[m][n]
}

func min(i,j int)int{
	if i<j{
		return i 
	}
	return j
}
// @lc code=end

